package immutablecollections;

import immutablecollections.ImSet.Bucket;
import immutablecollections.ImSet.Replace;
import immutablecollections.misc.*;
import java.io.*;
import java.util.*;
/**
 * An immutable version of `java.util.Map`.
 * 
 * ## Introduction
 *  
 * <img src=" doc-files/classes-focus-on-map.png" alt="classes" style="width: 40em"/></p>
 * 
 * A collection of {@link Entry} objects (key-value pairs).
 * 
 * As with `java.util.Map`, the fundamental methods are {@link #get}, {@link #put} and {@link #remove} although
 * `put()` and `remove` have a different meaning since
 * `ImMaps` are immutable.
 * 
 * Instead of modifying the map in place, {@link #put} creates a new map containing the new
 * key value pair and {@link #remove} creates a new map not containing it.
 * 
 * 
 * ### Examples:
 * Create an empty map:
 * 
 *     ImMap<String, String> mEmpty = new ImMap<String, String>();
 *     mEmpty.isEmpty()  =>  true
 * 
 * Put an entry:
 * 
 *     ImMap<String, String> mOne = mEmpty.put("a", "Aardvark");
 * 
 * The new map will have the entry
 * 
 *     mOne.size()    =>  1
 *     mOne.get("a")  =>  "Aardvark"
 * 
 * But the old one will be unchanged:
 * 
 *     mEmpty.isEmpty()  => true
 * 
 * Put another entry
 * 
 *     ImMap<String, String> mTwo = mOne.put("b", "Bear");
 *     
 * The new map, `mTwo` has two entries:
 * 
 *     mTwo.get("a")  => "Aardvark"
 *     mTwo.get("b")  => "Bear"
 * 
 * And, of course, `mOne` has not changed:
 * 
 *     mOne.size()    =>  1
 *     mOne.get("a")  =>  "Aardvark"
 *     mOne.get("b")  =>  null
 * 
 * You can remove entries:
 * 
 *     ImMap<String, String> mThree = mTwo.remove("a");
 *     mThree.get("a")  => null
 * 
 * If you remove them when they weren't there:
 * 
 *     ImMap<String, String> mFive = mTwo.remove("z");
 *     
 * The new map is the same as the old one:
 * 
 *     mFive == mTwo  =>  true
 * 
 * You can replace entries:
 * 
 *     ImMap<String, String> mFour = mTwo.put("b", "Buffalo");
 *     mFour.get("b")  =>  "Buffalo"
 * 
 * If you replace entries with identical ones then no new map is created - the old one is returned:
 * 
 *     ImMap<String, String> mSix = mTwo.put("b", "Bear");
 *     mSix == mTwo  =>  true
 * 
 * If you replace entries with *equal* but non identical entries then you get a new map:
 * 
 *      ImMap<String, String> mSeven = mTwo.put("b", "Bear".substring(1));
 *      mSeven == mTwo  =>  false
 * 
 * 
 * ## ImMaps are not Collections
 * 
 * Unlike most of the other collections in this library, this class does *not* implement the standard Java interface
 * {@link java.util.Collection} 
 * 
 */
public class ImMap<K, V> implements Iterable<ImMap.Entry<K, V>>, Serializable
{
    final private ImSet<Entry<K, V>> set;
    final private int hashCode;

    /**
     * The singleton empty map
     */
    final private static ImMap<?, ?> empty = new ImMap<Object, Object>();

    /**
     * The (singleton) empty map.
     * 
     */
    @SuppressWarnings("unchecked")
    public static <T, U> ImMap<T, U> empty()
    {
        return (ImMap<T, U>) empty;
    }

    /**
     * 
     * An `ImMap` entry (key-value pair).
     *
     */
    public static class Entry<KEY, VALUE> implements Serializable
    {
        final KEY key;
        final VALUE value;

        private Entry(final KEY key, final VALUE value)
        {
            this.key = key;
            this.value = value;
        }

        /**
         * `true` if `other` is an instance of `ImMap.Entry` and `this.key.equals(other.key)`.
         * 
         * This implementation is designed to allow `ImMap` to be implemented as an `ImSet<Entry>`.
         */
        @Override
        public boolean equals(final Object other)
        {
            return other instanceof Entry
                    ? key.equals(((Entry<?, ?>) other).key)
                    : false;
        }

        /**
         * The hash code value for `this`.
         * 
         * The algorithm is simply to return the hashCode of the key.
         *
         */
        @Override
        public int hashCode()
        {
            return key.hashCode();
        }

        /**
         * The key of this key-value pair.
         */
        public KEY getKey()
        {
            return key;
        }

        /**
         * The value of this key-value pair.
         * 
         * Note that it cannot be `null`.
         */
        public VALUE getValue()
        {
            return value;
        }
    }

    /**
     * The empty map.
     */
    public ImMap()
    {
        set = ImSet.empty();
        hashCode = 0;
    }

    private ImMap(final ImSet<Entry<K, V>> set, int hashCode)
    {
        this.set = set;
        this.hashCode = hashCode;
    }

    /**
     * The map with the same key-value pairs as `this` with the (possible) difference
     * that the key `key` is now mapped to `value`
     */
    public ImMap<K, V> put(final K key, final V value)
    {
        NullCheck.check(key);
        NullCheck.check(value);

        return putEntry(new Entry<K, V>(key, value));
    }

    private ImMap<K, V> putEntry(Entry<K, V> newEntry)
    {
        // We have to do the put in two steps so that we can calculate the new hash code
        ImTreeZipper<Bucket<Entry<K, V>>> path = set.getPathOn(newEntry);

        if (keyAndValueAreTheSameAsOld(path.getFocus().getElement(), newEntry))
            return this;

        ImSet<Entry<K, V>> newSet = set.addAtPath(newEntry, Replace.yes, path);

        return new ImMap<K, V>(newSet, hashCode + getMyHashOf(newEntry)
                - getMyHashOf(getEntryFromBucket(newEntry, path.getFocus().getElement())));
    }

    private boolean keyAndValueAreTheSameAsOld(Bucket<Entry<K, V>> bucket, Entry<K, V> newEntry)
    {
        Entry<K, V> oldEntry = getEntryFromBucket(newEntry, bucket);

        return oldEntry == null
                ? false
                : oldEntry.key == newEntry.key && oldEntry.value == newEntry.value;
    }

    private Entry<K, V> getEntryFromBucket(Entry<K, V> entryToGet, Bucket<Entry<K, V>> bucket)
    {
        return bucket == null
                ? null
                : bucket.get(entryToGet);
    }

    protected int getMyHashOf(Entry<K, V> oldEntry)
    {
        return oldEntry == null
                ? 0
                : oldEntry.key.hashCode() ^ oldEntry.value.hashCode();
    }

    /**
     * The value that `key` maps to (or `null` if no such mapping exists).
     */
    public V get(final K key)
    {
        final Entry<K, V> found = set.find(new Entry<K, V>(key, null));
        return found == null
                ? null
                : found.value;
    }

    /**
     * The map with the same key-value pairs as `this` with the (possible) difference
     * that the key `key` is now no longer mapped to `value`.
     */
    public ImMap<K, V> remove(final K key)
    {
        Entry<K, V> entry = new Entry<K, V>(key, null);

        // We have to do the remove in two steps so that we can calculate the new hash code
        Bucket<Entry<K, V>> bucketFound = set.getBucketContaining(entry);

        Entry<K, V> oldEntry = getEntryFromBucket(entry, bucketFound);

        return oldEntry == null
                ? this
                : new ImMap<K, V>(set.removeElementFromBucket(entry, bucketFound), hashCode() - getMyHashOf(oldEntry));
    }

    /**
     * An iterator on the key-value entries in `this`.
     */
    public Iterator<ImMap.Entry<K, V>> iterator()
    {
        return set.iterator();
    }

    /**
     * The number of key-value entries in `this`.
     */
    public int size()
    {
        return set.size();
    }

    /**
     * `true` iff `this` contains no entries.
     */
    public boolean isEmpty()
    {
        return size() == 0;
    }

    /**
     * `true` iff `other` is an instance of `ImMap` and `other` "contains the same entries" as `this`.
     * 
     *  More formally:
     *  
     *      other.size() == this.size()
     *      
     *  and for all `k` and `v` such that 
     *  
     *      v = this.get(k)
     * 
     *  then for all `j` such that `j` *equals* `k`:
     *  
     *      other.get(j)
     *      
     *  *equals* v.
     *  
     *  As usual, a *equals* b means:
     *  
     *      a.equals(b) == true
     *  
     */
    @SuppressWarnings("rawtypes")
    @Override
    public boolean equals(Object other)
    {
        if (this == other)
            return true;

        if (other instanceof ImMap)
        {
            ImMap otherMap = (ImMap) other;
            return size() == otherMap.size() && hasEqualEntries(otherMap);
        }

        return false;
    }

    @SuppressWarnings({ "rawtypes", "unchecked" })
    private boolean hasEqualEntries(ImMap other)
    {
        for (Entry entry : this)
        {
            if (!entry.value.equals(other.get(entry.key)))
                return false;
        }

        return true;
    }

    /**
     * The hash code value for `this`.
     *
     * Because `ImMaps` are immutable, the hash code is calculated only once when the map is
     * created and cached. Also, because each `ImMap` is constructed from another `ImMap`, the
     * hash code can be calculated efficiently.
     * 
     * The algorithm used is essentially the same as that used for {@link java.util.AbstractMap} so, if an
     * `AbstractMap` and an `ImMap`
     * contain "the same key-value pairs" then they will have the same hash code.
     * 
     */
    @Override
    public int hashCode()
    {
        return hashCode;
    }

}
